import heapq

class MyNode:
    def __init__(self, n: int):
        self.path = [0] * n  # 经过的节点路径
        self.marked = [False] * n # 路径是否经过某个节点
        self.first = 0   # 记录出发点
        self.last = 0    # 记录路径尾部节点
        self.lb = 0      # 目标估算函数值
        self.length = 0  # 已经走过的路径的长度
        self.cost = 0    # 已经走过的路径的代价

    # 判断路径中是否包含节点v
    def contains(self, v: int) -> bool:
        return self.marked[v]

    # 重写MyNode之间的大小比较方法。
    # 要使用优先队列结构，需要为数据类型提供比较大小的方式
    def __lt__(self, other) -> bool:
        return self.lb < other.lb

MAX = 10000

# 返回邻接矩阵i行上不在路径path中的最小元素
def getMinEdge(n: int, wg: list[list[int]], node: MyNode, i: int) -> int:
    return min((wg[i][j] for j in range(n) if not node.contains(j)), default=MAX)

# 返回邻接矩阵i行上的最小的两个元素之和
def getMin2Edge(n: int, wg: list[list[int]], i: int) -> int:
    i1 = min(range(n), key = lambda j: wg[i][j])
    min2 = min(x for j, x in enumerate(wg[i]) if j != i)
    return wg[i][i1] + min2

# 使用贪心法求上界
def getUper(n: int, wg: list[list[int]]) -> int:
    path = [0] * n # 记录经过的路径节点
    upper = 0      # 记录整个路径的权值
    path[0] = 0
    visited = [False] * n
    visited[0] = True # 从顶点0出发
    
    k = 1 # k为path路径的下标
    while k < n:
        minlen = MAX

        # 寻找path路径中前一个顶点到下一个顶点的最短路径
        for i in range(n):
            if not visited[i]:
            
                if wg[path[k - 1]][i] < minlen:
                    minlen = wg[path[k - 1]][i]
                    path[k] = i
        upper = upper + minlen # 记录已经经过的路径的权值
        visited[path[k]] = True
        k = k + 1  # 寻找下一个节点

    # 最后加上返回起点0的权值。由于是完全连通图，
    # 因此任意两个点之间均有边相连。
    upper = upper + wg[path[n - 1]][0]      
    return upper

# 求下界。计算方式为将邻接矩阵中每一行最小的两个元素相加求和后，再除以2
def getLower(n: int, wg: list[list[int]]) -> int:
    lower = 0
    for i in range(n):
        min2sum = getMin2Edge(n, wg, i)
        lower = lower + min2sum
    return lower // 2

# __main__
n = 5
# edges: 边权集
edges = [(0, 1, 15), (0, 2, 5), (0, 3, 25), (0, 4, 40), (1, 2, 30), (1, 3, 35), (1, 4, 45), (2, 3, 20), (2, 4, 10), (3, 4, 15)]
# wg: 邻接矩阵
wg = [[MAX] * n for _ in range(n)]
for u, v, w in edges:
    wg[u][v] = wg[v][u] = w
# 维护访问记录
visited = [False] * n

# 计算上界、下界
uper, lower = getUper(n, wg), getLower(n, wg)

# 初始化第一个节点，从顶点0开始
start = MyNode(n)        
start.first = 0
start.last = 0
start.lb = lower
start.path[0] = 0
start.marked[0] = True
start.length = 1
start.cost = 0

target = MyNode(n) # 最优解的叶子节点
pathCost = -1    # 最优路径长度

# 存储叶子节点的优先队列结构-PT表
hp = []
heapq.heappush(hp, start)

while hp:
    node = heapq.heappop(hp) # 将队列中lb值最小的元素出列
    if node.length == n - 1:
        # 边界场景，最后一个节点的场景需要特殊处理。
        # end代表最后一个结束节点
        # 将end置为没有出现在路径上的那个唯一剩余节点
        end = min(i for i in range(n) if not node.contains(i))           
        
        # 终点lb的计算需要考虑回到源点的代价
        lb = (2 * node.cost + wg[end][node.first] + wg[node.last][end]) // 2
        if lb < node.lb:
            node.cost = node.cost + wg[node.last][end]
            node.last = end
            node.marked[end] = True
            node.path[node.length] = end
            node.length = node.length + 1

            target = node
            pathCost = node.cost + wg[end][node.first]
            break
    
    for i in range(n):
        next = MyNode(n)
        if not node.contains(i): 
            for j in range(n):
                next.marked[j] = node.marked[j]
                next.path[j] = node.path[j]

            # 搜索当前节点的分支子节点
            next.first = node.first
            next.last = i
            next.marked[i] = True
            next.cost = node.cost + wg[node.last][i]
            
            next.path[node.length] = i
            next.length = node.length + 1

            p3 = 0   # p3代表目标函数中rj行最小的两个元素之和。计算p3
            for j in range(n):
                if not next.contains(j):
                    p3 = p3 + getMin2Edge(n, wg, j)

            # 计算叶子节点的lb值
            next.lb = (2 * next.cost + getMinEdge(n, wg, next, 
                next.path[next.length - 1])+ getMinEdge(n, wg, next, 0) + p3) // 2

            # 满足上下界的节点加入到优先队列中
            if next.lb <= uper:
                heapq.heappush(hp, next)

# 输出最优解路径
print(*target.path, sep='->', end='->0\n')

# 输出该路径代价
print('路径长度:', pathCost)
